package acwing._1_1AlgorithmBasic._3SearchGraph;
/**
 * @Project : AlgorithmLearning
 * @Package : ACWing._1_1AlgorithmBasic
 * @File : Q0849.java
 * @Author : WangRuoyu
 * @Date : 2023/3/29 15:04
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Q0849 {
    static int n;
    static int m;
    static int[][] p;

    public static int[] dijkstra1(int x) {
        int[] dist = new int[n + 1];
        boolean[] st = new boolean[n + 1];
        Arrays.fill(dist, (int) 1e9);
        dist[x] = 0;

        for (int i = 1; i < n; ++i) {
            int index = -1;
            for (int j = 1; j <= n; ++j) {
                if (!st[j] && (index == -1 || (dist[index] > dist[j]))) {
                    index = j;
                }
            }
            st[index] = true;
            for (int j = 1; j <= n; ++j) {
                dist[j] = Math.min(dist[j], dist[index] + p[index][j]);
            }
        }
        return dist;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] words = br.readLine().split(" ");
        n = Integer.parseInt(words[0]);
        m = Integer.parseInt(words[1]);
        p = new int[n + 1][n + 1];
        for (int i = 0; i < p.length; ++i) {
            Arrays.fill(p[i], (int) 1e9);
            p[i][i] = 0;
        }
        for (int i = 0; i < m; ++i) {
            words = br.readLine().split(" ");
            int a = Integer.parseInt(words[0]);
            int b = Integer.parseInt(words[1]);
            int w = Integer.parseInt(words[2]);
            if (a != b) {
                p[a][b] = Math.min(p[a][b], w);
            }
        }
        int[] w = dijkstra1(1);
        if (w[n] == (int) 1e9) {
            System.out.println(-1);
            return;
        }
        System.out.println(w[n]);
    }
}
